public class Day16 {
    public static void main(String[] args) {
        int[] a = {1,2,4,3,5,4,7,2};
        findNumberOfLIS(a);
    }
    public static int findNumberOfLIS(int[] nums) {
        int n = nums.length;
        int[] f = new int[n];
        int[] g = new int[n];
        for(int i=0;i<n;i++) {
            f[i]=g[i]=1;
        }
        int maxLen = 1;//表示当前最长的递增子序列
        int ret = 0;//记录结果返回值
        for(int i=1;i<n;i++) {
            for(int j=i-1;j>=0;j--) {
                if(nums[i] > nums[j]) {
                    //得到一个子串
                    if(f[j]+1 > f[i]) {
                        f[i]=f[j]+1;
                        g[i]=g[j];
                    }else if(f[j]+1 == f[i]) {
                        g[i]+=g[j];
                    }
                }
            }
            maxLen = Math.max(maxLen,f[i]);
        }
        for(int i=0;i<n;i++) {
            if(f[i] == maxLen) {
                ret+=g[i];
            }
        }
        return ret;
    }

}
